let oUl = document.querySelector('#ul1');
let oLi = document.getElementsByTagName('li');
let oInput = document.querySelector('input');
let beginLi = oUl.getElementsByClassName('sty1');
let endLi = oUl.getElementsByClassName('sty2');

let map = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
];


// 开方值
let colos = Math.sqrt(map.length);
// 网格大小
let sizeGird = 20;
let openArr = [];
let closeArr = [];

init();

function init() {
    // 创建map
    createMap();
    // 点击按钮
    oInput.onclick = function () {
        openFn();
    }
}

function createMap() {
    oUl.style.width = colos * (sizeGird + 1) + 1 + 'px';

    for (let i = 0; i < map.length; i++) {
        let li = document.createElement('li');
        li.style.width = sizeGird + 'px';
        li.style.height = sizeGird + 'px';
        oUl.appendChild(li);

        if (map[i] == 1) {
            li.classList.add('sty1');
            // 起始队列
            openArr.push(li);
        } else if (map[i] == 2) {
            li.classList.add('sty2');
        } else if (map[i] == 3) {
            li.classList.add('sty3');
            // 关闭队列
            closeArr.push(li);
        }
    }
}

function openFn() {
    // 取出添加到结束队列
    let nowLi = openArr.shift();

    if (nowLi == endLi[0]) {
        showLine();
        return;
    }

    closeFn(nowLi);
    // 获得当前起始位置周边可走位置的格子
    findLi(nowLi);
    openArr.sort(function (li1, li2) {
        return li1.num - li2.num;
    });

    openFn();
}

// 寻找起始位置周边的位置
function findLi(nowLi) {

    let result = [];
    for (let i = 0; i < oLi.length; i++) {
        if (filter(oLi[i])) {
            result.push(oLi[i]);
        }
    }

    function filter(li) {

        for (let i = 0; i < closeArr.length; i++) {
            if (closeArr[i] == li) {
                // 比对成功不是我们想要的
                return false;
            }
        }

        for (let i = 0; i < openArr.length; i++) {
            if (openArr[i] == li) {
                return false;
            }
        }
        return true;
    }

    // 去没有障碍物的节点中找相邻的
    // abs方法可返回数的绝对值
    // sizeGird + 1边框的值
    for (let i = 0; i < result.length; i++) {
        if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= sizeGird + 2) &&
            (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 2)) {
            // 拿到相邻的满足条件的添加到openArr中   
            result[i].num = f(result[i]);
            result[i].parent = nowLi;
            openArr.push(result[i]);
        }
    }
}

function showLine() {
    let result = [];
    let lastLi = closeArr.pop();
    let iNow = 0;

    findParent(lastLi);

    function findParent(li) {
        result.unshift(li);
        if (li.parent == beginLi[0]) {
            return;
        }
        findParent(li.parent);
    }

    let temer = setInterval(() => {
        result[iNow].style.background = 'red';
        iNow++;
        if (iNow == result.length) {
            clearInterval(temer);
        }
    }, 500);
}

function closeFn(nowLi) {
    closeArr.push(nowLi);
}

// 估价函数
function f(nodeLi) {
    return g(nodeLi) + h(nodeLi);
}

function g(nodeLi) {
    // 计算坐标差值
    let a = beginLi[0].offsetLeft - nodeLi.offsetLeft;
    let b = beginLi[0].offsetTop - nodeLi.offsetTop;
    // 勾股定理 a边平方 b边平方 开方
    return Math.sqrt(a * a + b * b);
}

function h(nodeLi) {
    // 计算坐标差值
    let a = endLi[0].offsetLeft - nodeLi.offsetLeft;
    let b = endLi[0].offsetTop - nodeLi.offsetTop;
    // 勾股定理 a边平方 b边平方 开方
    return Math.sqrt(a * a + b * b);
}
